An available bandwidth (also referred to as a usable bandwidth) of a communication line is an unused bandwidth that is obtained by subtracting other traffic flowing through the network (hereinafter referred to as cross traffic) from a physical bandwidth at a bottleneck link on the communication line. For example, when a physical bandwidth at a bottleneck link on a communication line is 100 Mbps and cross traffic is 30 Mbps, the available bandwidth 100 is 100−30=70 Mbps.
Estimation of an available bandwidth is important in applications such as video chats, videophone conversations and videoconferences in which videos are bi-directionally exchanged between terminals to communicate with each other. This is because keeping the transmission rate of video below or equal to the estimated available bandwidth makes it possible to minimize packet losses that would occur when the sum of the transmission rate of video and cross traffic exceeds the physical bandwidth at a bottleneck link on the communication line, and to ensure video quality.
In the invention of PTL 1, a transmitting-side device transmits a plurality of packets combined together in one (hereinafter referred to as a packet train) to a receiving-side device, with each of the packets for available bandwidth estimation being arranged at equal transmitting intervals and gradually increasing in packet size, as illustrated in FIG. 1. Further, the receiving-side device detects a change in the receiving interval between packets in the received packet train to estimate an available bandwidth. When the transmitting rate of packets exceeds an available bandwidth on the network while the packet train 10 illustrated in FIG. 1 is passing through the network, the packets in the packet train 10 are temporarily queued in a device, such as a router or a switch, on the network (hereinafter, a delay due to queueing will be referred to as a queueing delay). When a queueing delay occurs, the receiving interval between packets at the receiving device will be greater than the transmitting interval at the transmitting device. For example, the receiving interval between packet 3 and packet 4 in the packet train 11 illustrated in FIG. 1 is greater than the transmitting interval. The invention of PTL 1 takes advantage of this characteristic to identify a point at which the receiving interval between packets at the receiving-side device starts becoming greater than the transmitting interval at the transmitting-side device and calculates an available bandwidth by dividing a packet size corresponding to the point by the transmitting interval.
As illustrated in FIG. 2, delays that occur in packet communication can be classified into four types: 1. propagation delay, 2. processing delay, 3. queueing delay, and 4. serialization delay. A serialization delay is sometimes also referred to as transmission delay.
A propagation delay is the time required for a signal to propagate through a communication line at a speed close to the speed of light. A processing delay is the time required for determining a communication line through which packets are sent out by referring to a routing table within a device such as a router or a switch when the device receives the packets. A queueing delay is as described above. A serialization delay is the time required for transmitting all of the bits of a packet to a communication line and can be calculated by dividing its packet size by the physical bandwidth on the communication line. In other words, the serialization delay increases as the packet size increases.
The invention of PTL 1 aims to prevent degradation of the estimation precision of an available bandwidth on a network. Here, noise occurs on the network, for example, when cross traffic changes while a packet train is being transmitted, when the radio field intensity on a wireless network changes, or when transmitting and receiving timings of packets go wrong due to an influence of scheduling at a base station.
The invention of PTL 1 analyzes a broad trend of queueing delays of a plurality of packets from a macroscopic viewpoint since the invention is largely influenced by noise when checking receiving intervals or queueing delays from a microscopic viewpoint for each packet. Thus, the invention of PTL 1 can reduce the influence of noise during identification of a rising position of a queueing delay.
According to the invention of PTL 1, a specific method for identifying a point at which the packet receiving interval starts to increase is as follows. Note that the increase in packet receiving interval mentioned above is caused by an increase in a queueing delay.
The invention of PTL 1 first calculates: queueing delay={tr(i)−t (i−1)}−{ts(i)−ts(i−1)} (Formula 1). Here, ts(i) is the transmitting time at which the i-th packet (i=1, 2, . . . , N) is transmitted from the transmitting-side device, where N is the number of packets in a packet train. In addition, tr(i) is the reception time of the i-th packet (i=1, 2, . . . , N) at the receiving-side device, where N is the number of packets in the packet train.
In other words, the invention of PTL 1 defines a queueing delay as the difference in the times elapsed from a previous packet. In this case, an ideal progression of a queueing delay to be assumed in the total absence of the noise is a line of a horizontal straight line and a sloped straight line connected together. The invention of PTL 1 calculates, for each of a plurality of ideal curves each of which is a line of the horizontal straight line and a sloped straight line connected together, the sum of squared errors with a queueing delay calculated according to Formula 1. The invention of PTL 1 then identifies an ideal curve that yields the smallest sum of squared errors calculated. Further, the invention of PTL 1 identifies the connection point between the horizontal straight line and the sloped straight line in the ideal curve that best fits the queueing delay, the connection point being identified as the rising position of the queueing delay viewed from a macroscopic viewpoint.
Here, when integrating and rewriting Formula 1 as the elapsed time from the starting packet, Formula 1 is: queueing delay Q(i)={tr(i)−tr(1)}−{ts(i)−ts(1)}. Note that progression of queueing delay Q(i) to be assumed in the total absence of noise is a line of the horizontal straight line and a parabola connected together. The reason is as follows. First, since queueing delay does not occur when a transmitting rate for each packet is lower than the true value of an available bandwidth, ideal progression of queueing delay Q(i) is represented by a horizontal straight line. Further, when the transmitting rate for each packet exceeds the true value of the available bandwidth, ideal progression of queueing delay Q(i) rises in parabolic shape and thus the ideal progression of queueing delay Q(i) forms a parabola.
FIG. 3 illustrates a method for identifying the rising position of the queueing delay Q(i) described above (hereinafter referred to as the second identification method). The second identification method plots queueing delay Q(i) 12 on a plane surface with packet numbers i on the horizontal axis and queueing delay Q(i) on the vertical axis as illustrated in FIG. 3. Further, the second identification method plots ideal curves 13 as many as the number of packets, each of the ideal curves being a horizontal straight line and a parabola connected together provided that the ideal progression of queueing delay Q(i) is assumed in the total absence of noise. Note that only five ideal curves 13 are illustrated in FIG. 3, while there are (N−1) ideal curves where N is the number of packets in a packet train.
The second identification method then calculates, for each of the ideal curves 13, the sum of squared errors between each of the ideal curves 13 and the queueing delay Q(i) 12. Further, the second identification method identifies the ideal curve 13-4 that yields the smallest sum of squared errors as in FIG. 3. Lastly, the second identification method identifies the connection point between the horizontal straight line and the parabola of the ideal curve 13-4 that best fits the observed queueing delay 12, the connection point being identified as the rising position of the queueing delay viewed from a macroscopic viewpoint.